/**
 * 1.三数之和：给你一个包含n个整数数组nums，判断nums中是否存在三个元素a、b、c，是的a+b+c=0?
 *  请找出所有和为0且不重复的三元数组。注意[0,0,0]的情况
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    let rtn = [];
    if (nums.length < 3) {
        return rtn;
    } 
    nums.sort((a, b) => a - b);
    if (nums[0] > 0 || nums[nums.length - 1] < 0) {
        return rtn;
    }
    // console.log(nums);
    let left, right;
    for (let i = 0; i < nums.length - 2; i++) {
        if (nums[i] <= 0) {
            left = i + 1;
            right = nums.length - 1;
            while (left < right && nums[right] >= 0) {
                let sum = nums[i] + nums[left] + nums[right];
                if (sum > 0) {
                    --right;
                } else if (sum < 0) {
                    ++left;
                } else {
                    rtn.push([nums[i], nums[left], nums[right]]);
                    while (left < right && nums[right] === nums[right - 1]) {
                        --right;
                    }
                    while (left < right && nums[left] === nums[left + 1]) {
                        ++left;
                    }
                    --right;
                    ++left;
                }
            }
            while (nums[i] === nums[i + 1]) {
                ++i;
            }
        } else {
            break;
        }
    }
    return rtn;
};
/**
 * 2.给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
var setZeroes = function(matrix) {
    let m = matrix.length,
        n = matrix[0].length;

    // 使用一个标记变量
    let flag_c0 = false;
    for (let i = 0; i < m; i++) {
        if (matrix[i][0] === 0) {
            flag_c0 = true;
        }
        for (let j = 1; j < n; j++) {
            if (matrix[i][j] === 0) {
                matrix[i][0] = matrix[0][j] = 0;
            }
        }
    }
    for (let i = m - 1; i >= 0; i--) { // 注意：从最后一行遍历，避免污染第一行标记
        for (let j = 1; j < n; j++) {
            if (matrix[i][0] === 0 || matrix[0][j] === 0) {
                matrix[i][j] = 0;
            }
        }
        if (flag_c0) {
            matrix[i][0] = 0;
        }
    }

    // // 使用两个标记变量
    // let flag_r = false,
    //     flag_c = false;
    // for (let i = 0; i < m; i++) {
    //     if (matrix[i][0]) {
    //         flag_c = true;
    //         break;
    //     }
    // }
    // for (let i = 0; i < n; i++) {
    //     if (matrix[0][i]) {
    //         flag_r = true;
    //         break;
    //     }
    // }
    // for (let i = 1; i < m; i++) {
    //     for (let j = 1; j < n; j++) {
    //         if (matrix[i][j] === 0) {
    //             matrix[i][0] = matrix[0][j] = 0;
    //         }
    //     }
    // }
    // for (let i = 1; i < m; i++) {
    //     for (let j = 1; j < n; j++) {
    //         if (matrix[i][0] === 0 || matrix[0][j] === 0) {
    //             matrix[i][j] = 0;
    //         }
    //     }
    // }
    // if (flag_r) {
    //     for (let i = 0; i < m; i++) {
    //         matrix[i][0] = 0;
    //     }
    // }
    // if (flag_c) {
    //     for (let i = 0; i < n; i++) {
    //         matrix[0][i] = 0;
    //     }
    // }
    
    // // 使用标记数组
    // let row = new Array(m),
    //     col = new Array(n);
    // for (let i = 0; i < m; i++) {
    //     for (let j = 0; j < n; j++) {
    //         if (matrix[i][j] === 0) {
    //             row[i] = col[j] = true;
    //         }
    //     }
    // }
    // for (let i = 0; i < m; i++) {
    //     for (let j = 0; j < n; j++) {
    //         if (row[i] || col[j]) {
    //             matrix[i][j] = 0;
    //         }
    //     }
    // }
    return matrix;
};
/**
 * 3.给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
 *  字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母都恰好只用一次。
 * @param {string[]} strs 仅包含小写字母
 * @return {string[][]}
 */
var groupAnagrams = function(strs) {
    let map = {};
    let a = 'a'.charCodeAt();
    // 计数
    for (const str of strs) {
        let arr = [];
        for (const c of str) {
            let index = c.charCodeAt() - a;
            arr[index] ? ++arr[index] : (arr[index] = 1);
        }
        let key = arr.map(function(item, i) {
            return String.fromCharCode(a + i) + item;
        }).join();
        if (map.hasOwnProperty(key)) {
            map[key].push(str);
        } else {
            map[key] = [str];
        }
    }
    // 排序
    // for (let str of strs) {
    //     let k = str.split('').sort().join('');
    //     if (map.hasOwnProperty(k)) {
    //         map[k].push(str);
    //     } else {
    //         map[k] = [str];
    //     }
    // }
    return Object.values(map);
};

/**
 * 4.给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
 * @param {string} s  由英文字母、数字、符号和空格组成
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    let i = 0,
        j = 0,
        len = s.length,
        maxS = 0;
    let cache = new Map();
    while (j < len) {
        let c = s[j];
        if (cache.has(c)) {
            maxS = Math.max(maxS, j - i);
            let prevI = cache.get(c);
            while (i <= prevI) {
                cache.delete(s[i]);
                ++i
            }
        }
        cache.set(c, j++);
    }
    maxS = Math.max(maxS, j - i);
    return maxS;
};
/**
 * 动态规划没看懂
 * 5.给你一个字符串 s，找到 s 中最长的回文子串。
 * @param {string} s 仅由数字和英文字母（大写和/或小写）组成
 * @return {string}
 */
var longestPalindrome = function(s) {
    // 中心扩展法：一个回文字符串两边字符相同，那么这个也一定是字符串
    if (s.length < 2) {
        return s;
    }
    let start = 0, end = 0;
    for (let l = 0; l < s.length; l++) {
        let len1 = expandAroundCenter(s, l, l);
        let len2 = expandAroundCenter(s, l, l + 1);
        let len = Math.max(len1, len2);
        if (len > end - start) {
            start = l - Math.floor((len - 1) / 2);
            end = l + Math.floor(len / 2);
        }
    }
    return s.slice(start, end + 1);
    
    // 暴力破解
    // let maxS = '';
    // for (let i = 0; i < s.length; i++) {
    //     let tmp = s[i];
    //     for (let j = i+1; j < s.length; j++) {
    //         tmp += s[j];
    //         if (tmp === tmp.split('').reverse().join('')) {
    //             maxS = maxS.length >= tmp.length ? maxS : tmp; 
    //         }
    //     }
    // }
    // return maxS ? maxS : s[0];
};
var expandAroundCenter = function(str, i, j) {
    while (i >= 0 && j < str.length && str[i] === str[j]) {
        --i;
        ++j;
    }
    return j - i - 1;
}
/**
 * 6.给你一个整数数组 nums ，判断这个数组中是否存在长度为 3 的递增子序列。
 *  如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k ，使得 nums[i] < nums[j] < nums[k] ，返回 true ；否则，返回 false 。
 * @param {number[]} nums
 * @return {boolean}
 */
var increasingTriplet = function(nums) {
    let min = mid = Number.MAX_SAFE_INTEGER;
    // 注意判断条件 <= 是为了把最小值拦截当前层
    for (const n of nums) {
        if (n <= min) {
            min = n;
        } else if (n <= mid) {
            mid = n;
        } else if (n > mid) {
            return true;
        }
    }
    return false;
};

// console.log(increasingTriplet([2,1,5,0,4,6]));